Masala #R103E

Xotira 512 MB Vaqt 1000 ms Qiyinchiligi 1 %

Kvadrat uchburchak

Sizga \(n \cdot n\) \(a\) jadval berilgan, va sehirgar agar siz \(q\) ta so'rov ga javob bersangiz shokolad beraman deb vada berdi, afsuski sehirgar uhlashni juda hohlab turgani uchun siz unga tez javob berishingiz kerak har bir so'rov da:

\(l\) va \(r\) \((l \le r)\)beriladi sizni vazifangiz shunday \(a_{i, j}\) lar summasini topshingiz kerak \(l≤i≤j≤r\) sharti bajariladi. Rasmiy ravishda:

\[\sum_{i=l}^{r} \sum_{j=i}^{r} a_{i,j}\]

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) va \(q\)( \(1 \le n \le 2500\), \(1 \le q \le 200000\)) - satr va qatorni uzunligi va so'rovlar soni.

Keyingi \(n\) qatorda jadval \(a\)(\(a_{i,j} \le 10^9\)).

Keyingi \(q\) qatorda so'rovlar, har bir so'rovda \(l\) va \(r\) beriladi(\(1 \le l \le r \le n\))

Chiquvchi ma'lumotlar:

Har bir so'rovga javobni chiqaring - bitta butun son.

Misollar

#	input.txt	output.txt
1	3 5 15 19 11 18 20 3 9 4 4 1 2 1 1 1 2 3 3 2 2	54 15 54 4 20
2	6 7 2 1 1 1 19 5 16 13 16 7 19 8 10 2 14 14 16 13 3 7 3 16 10 4 8 12 12 1 16 17 18 12 10 6 5 4 4 4 4 5 3 6 2 3 4 4 1 2 1 5	16 42 124 43 16 16 165

input.txt

output.txt

6 7
2 1 1 1 19 5
16 13 16 7 19 8
10 2 14 14 16 13
3 7 3 16 10 4
8 12 12 1 16 17
18 12 10 6 5 4
4 4
4 5
3 6
2 3
4 4
1 2
1 5

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin